package com.test.daily.leetcode.y2022.m05.day0518.v04;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/5/18 上午 11:38
 * @version: 1.0
 */
public class HeapGreater<T> {

    HashMap<T, Integer> indexMap;
    ArrayList<T> heap;
    int heapSize;
    Comparator com;

    public HeapGreater(Comparator c) {
        this.com = c;
        indexMap = new HashMap<>();
        heap = new ArrayList<>();
    }

    public boolean contains(T obj) {
        return indexMap.containsKey(obj);
    }

    public void push(T obj) {
        heap.set(heapSize, obj);
        indexMap.put(obj, heapSize);
        heapInsert(heapSize++);
    }

    public T pop() {
        T ans = heap.get(0);
        swap(0, heapSize - 1);
        indexMap.remove(ans);
        heap.remove(--heapSize);
        heapify(0);
        return ans;
    }

    public T remove(T obj) {
        T replace = heap.get(heapSize - 1);
        int index = indexMap.get(obj);
        indexMap.remove(obj);
        heap.remove(--heapSize);
        if (replace != obj) {
            heap.set(index, replace);
            indexMap.put(replace, index);
            resign(index);
        }
        return replace;
    }

    public void resign(int index) {
        heapify(index);
        heapInsert(index);
    }

    public void swap(int index1, int index2) {
        T obj1 = heap.get(index1);
        T obj2 = heap.get(index2);
        heap.set(index1, obj2);
        heap.set(index2, obj1);
        indexMap.put(obj1, index2);
        indexMap.put(obj2, index1);
    }

    public void heapInsert(int index) {
        while (com.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
            swap(index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public void heapify(int index) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize && com.compare(heap.get(left), heap.get(left + 1)) < 0 ? left + 1 : left;
            largest = com.compare(heap.get(index), heap.get(largest)) < 0 ? largest : index;
            if (index == largest) {
                break;
            }
            swap(index, largest);
            index = largest;
            index = index * 2 + 1;
        }
    }
}
